// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2002 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: bitvector.icc,v 1.11 2010-03-11 15:16:39 carzanig Exp $
//
#include <cstddef>

#include "bitcounter.h"

namespace siena {

inline ibitvector::block::block(index *idx) throw() : up(idx) {
    for(size_t i = 0; i < block_size; ++i)
	elements[i] = 0;
}

inline ibitvector::index::index(index *idx) throw() : up(idx) {
    for(size_t i = 0; i < index_size; ++i) {
	down[i].i = NULL;
	down[i].b = NULL;
    }
}

inline ibitvector::ibitvector() throw()
    : count(0), size(0), first_block(NULL) {}

inline size_t ibitvector::get_count() const throw() { return count; }
inline size_t ibitvector::get_size() const throw() { return size + 1; }

inline void ibitvector::clear() throw() {
    count = 0;
    size = 0;
    first_block.up = NULL;
    for(register size_t i = 0; i < block_size; ++i)
	first_block.elements[i] = 0;
}

inline bitvector::bitvector(const bitvector & x) throw() 
    : size(x.size), count(x.count) {
    size_t s = atom_size(size);
    elements = new bv_atom_t[s];
    while(s-- > 0) {
	elements[s] = x.elements[s];
    }
}

inline bitvector::bitvector(size_t s, bool v) throw() : size(s), count(0) {
    s = atom_size(size);
    elements = new bv_atom_t[s];
    bv_atom_t value = 0;
    if (v) { 
	value = ~value;
	count = size;
    }
    while(s-- > 0) {
	elements[s] = value;
    }
}

inline bitvector::bitvector(bv_atom_t * e, size_t s, bool v) throw()
    : elements(e), size(s), count(0) {
    s = atom_size(size);
    bv_atom_t value = 0;
    if (v) { 
	value = ~value;
	count = size;
    }
    while(s-- > 0) {
	elements[s] = value;
    }
}

inline bitvector::bitvector(bv_atom_t * e, const bitvector & x) throw() 
    : elements(e), size(x.size), count(x.count) {
    size_t s = atom_size(size);
    while(s-- > 0) {
	elements[s] = x.elements[s];
    }
}

inline bitvector & bitvector::operator = (const bitvector & x) throw() {
    size_t s = atom_size(size);
    count = x.count;
    while(s-- > 0) {
	elements[s] = x.elements[s];
    }
    return *this;
}

inline unsigned int atom_bit_count(bv_atom_t x) {
    unsigned int res = 0;
    while(x) {
	res += BitCounterMap[x & 255];
	x >>= 8;
    }
    return res;
}

inline bitvector & bitvector::operator &= (const bitvector & x) throw() {
    size_t s = atom_size(size);
    while(s-- > 0 && count > 0) {
	count -= atom_bit_count(elements[s]);
	elements[s] &= x.elements[s];
	count += atom_bit_count(elements[s]);
    }
    return *this;
}

inline bool bitvector::operator < (const bitvector & x) const throw() {
    for(size_t i = 0; i < atom_size(size); ++i) {
	if (elements[i] < x.elements[i]) {
	    return true;
	} else if (elements[i] > x.elements[i]) {
	    return false;
	} 
    }
    return false;
}

inline bool bitvector::operator == (const bitvector & x) const throw() {
    if (count != x.count) return false;
    size_t s = atom_size(size);
    while(s-- > 0) {
	if (elements[s] != x.elements[s]) {
	    return false;
	} 
    }
    return true;
}

inline bitvector::~bitvector() throw() {
    delete [] elements;
}

inline size_t bitvector::get_count() const throw() { return count; }
inline size_t bitvector::get_size() const throw() { return size; }

inline bool bitvector::operator[](register size_t pos) const throw() {
    size_t i = atom_position(pos);
    if (i >= size) return false;
    register bv_atom_t atom_mask = 1;
    atom_mask <<= bit_position(pos);
    return (elements[i] & atom_mask);
}

inline bool bitvector::test(register size_t pos) const throw() {
    size_t i = atom_position(pos);
    if (i >= size) return false;
    register bv_atom_t atom_mask = 1;
    atom_mask <<= bit_position(pos);
    return (elements[i] & atom_mask);
}

inline bool bitvector::set(register size_t pos) throw() {
    unsigned int i = atom_position(pos);
    if (i >= size) return false;
    register bv_atom_t atom_mask = 1;
    atom_mask <<= bit_position(pos);
    if ((elements[i] & atom_mask)) {
	return true;
    } else {
	elements[i] |= atom_mask;
	++count;
	return false;
    }
}

inline bool bitvector::clear(register size_t pos) throw() {
    unsigned int i = atom_position(pos);
    if (i >= size) return false;
    register bv_atom_t atom_mask = 1;
    atom_mask <<= bit_position(pos);
    if ((elements[i] & atom_mask)) {
	elements[i] &= ~atom_mask;
	--count;
	return false;
    } else {
	return true;
    }
}

inline ibitvector::iterator::iterator(const block & b) throw() 
    : bi(b.up), addr(0), level(0) {}

inline size_t ibitvector::iterator::element_address() const throw() {
    return addr * block_size;
}

inline const ibitvector::block * ibitvector::iterator::next_block() throw() {
    while (bi != NULL) {
	++addr;
	if ((addr % index_size) != 0) {
	    if (level == 0) {
		if (bi->down[addr % index_size].b != NULL)
		    return bi->down[addr % index_size].b;
	    } else {
		if (bi->down[addr % index_size].i != NULL) {
		    bi = bi->down[addr % index_size].i;
		    addr *= index_size;
		    --level;
		}
	    }
	} else {
	    //
	    // end of index at this level
	    //
	    bi = bi->up;
	    ++level;
	    addr /= index_size;
	}
    }
    return NULL;
}

inline size_t bitvector::set(bv_atom_t * x, 
			     bv_atom_t * xend, 
			     const bv_atom_t * y, 
			     const bv_atom_t * yend) throw() {
    register size_t result = 0;
    register bv_atom_t diff;

    while (x != xend && y != yend) {
	if (*y != 0) {
	    for(diff = (*x & *y) ^ *y; // the bits of y that are not in x 
		diff != 0; diff >>= CHAR_BIT)
		result += BitCounterMap[diff & BitCounterMapMask];
	    *x |= *y;
	}
	++x;
	++y;
    }
    return result;
}

} // end namespace siena
